package com.leetcode;

import com.leetcode.common.TreeNode;

/**
 * 98. 验证二叉搜索树
 * 递归迭代 另一种方法
 *
 * 如果该二叉树的左子树不为空，则左子树上所有节点的值均小于它的根节点的值；
 * 若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值；它的左右子树也为二叉搜索树。
 *
 * @author fy
 * @date 2022/4/26 13:53
 */
public class Solution98_1 {

    public boolean isValidBST(TreeNode root) {
        // 这里需要注意, 超出int数据范围的陷阱, 需要改成long类型
        return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    private boolean isValidBST(TreeNode root, long lower, long higher) {
        if (root == null) {
            return true;
        }
        // 当前这棵树上下界的范围
        if (root.val >= higher || root.val <= lower) {
            return false;
        }
        // 左子树的上界范围变为root.val, 右子树下界范围变为root.val
        return isValidBST(root.left, lower, root.val)
                && isValidBST(root.right, root.val, higher);
    }

}
